package cn.qyd.kaoshi;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author 邱运铎
 * 最小覆盖子串
 * @date 2024-03-24 12:21
 */
public class MinSonStr {
    public static void main(String[] args) {
//        String s = "ADOBECODEBANC";
//        String t = "ABC";
        String s = "abc";
        String t = "ac";
        int sLen = s.length();
        int tLen = t.length();
        String result = "";
        String str = "";
        HashMap<Character, Integer> tMap = new HashMap<>();
        for (int i = 0; i < tLen; i++) {
            tMap.put(t.charAt(i),tMap.getOrDefault(t.charAt(i),0) - 1);
        }
        System.out.println(tMap);
        hasFind:
        for (int i = tLen; i <= sLen; i++) {
            for (int j = 0; j + i <= sLen; j++) {
                str = s.substring(j,j+i);
                if (isSonStr(str,new HashMap<Character,Integer>(tMap))) {
                    result = str;
                    break hasFind;
                }
            }
        }

        System.out.println( result);
    }

    public static boolean isSonStr(String str, HashMap<Character,Integer> tMap) {
        for (int i = 0; i < str.length(); i++) {
            char key = str.charAt(i);
            if (tMap.containsKey(key)) {
                tMap.put(key,tMap.get(key) + 1);
                System.out.println(str + "-----" + i  + "     " + key);
                System.out.println(tMap);
                if (tMap.get(key) == 0) {
                    tMap.remove(key);
                    if (tMap.isEmpty()) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}